package 回溯;
/**
 * 这个跟 左程云的  facebook 面试题 还不一样 我靠
 * 明显 这个 讨论的  情况 更多一些 
 * 暴力 递归   leetcode 第一个 样例 就超时 了 (我敲 )
 *但是 我很 开心 因为 一遍 就成功  (没有 怎么调试 )
 *记忆化 搜索会不会 超时 ???
 */
public class leetcode2266回溯dpdouke {
	static int  cons= 1000000007; // or (int) ( 1e9  +  7)
	public static void main(String []args) {
//		String s = "22233"; 2082876103 
		/**
		 * 下面 这个 样例  15 s (我敲)
		 */
		String s = "222222222222222222222222222222222222";
//		System.out.println((int)(1e9 + 7));
//		System.out.println(solution(s.toCharArray(),0,s.length()));
		long t1 = System.currentTimeMillis();
		System.out.println(solutionDp(s));
		long t2 = System.currentTimeMillis();
		System.out.println(t2 - t1);
	}

/*
 2023/ 6 / 7
 */
	public int process(int index,String s){
		if (index == s.length()) {
			return 1;
		}
		long ans = 0;

		ans += process(index + 1,s); // 当前字符 肯定是可以的！ 无论是哪种情况！ // 一些公共的 决策 可以 直接 提到 公共的 地方执行 ， 特殊的 决策 特殊处理  就行！

		if(index + 1 < s.length() && s.charAt(index) == s.charAt(index + 1)){
			ans += process(index + 2,s);
		}

		if(index + 2 < s.length() && s.charAt(index) == s.charAt(index + 1) && s.charAt(index + 1) == s.charAt(index + 2)){
			ans += process(index + 3,s);
		}

		if(s.charAt(index) == '7' || s.charAt(index) == '9'){
//            ans += process(index + 1,s);
//            if(index + 1 < s.length() && s.charAt(index) == s.charAt(index + 1)){
//                ans += process(index + 2,s);
//            }
//            if(index + 2 < s.length() && s.charAt(index) == s.charAt(index + 1) && s.charAt(index + 1) == s.charAt(index + 2)){
//                ans += process(index + 3,s);
//            }
			if(index + 3 < s.length() &&s.charAt(index) == s.charAt(index + 1) && s.charAt(index + 1) == s.charAt(index + 2) && s.charAt(index) == s.charAt(index + 3)){
				ans += process(index + 4,s);
			}
		}
//        else{
//            if(index + 1 < s.length() && s.charAt(index) == s.charAt(index + 1)){
//                ans += process(index + 2,s);
//            }
//            if(index + 2 < s.length() && s.charAt(index) == s.charAt(index + 1) && s.charAt(index + 1) == s.charAt(index + 2)){
//                ans += process(index + 3,s);
//            }
//        }

		ans = ans % 1000_000_007;
		return (int)ans;
	}





	/**
	 * 
	 * 暴力递归(其实 也能 感觉出来) 
	 * 很慢 
	 */
		static int solution(char[] s,int index,int len) {
			if(index > len )
				return 0;
			if(index == len)
				return 1;
/**			for()
			int ans = 0;
			if(index > 0) {
				ans += solution(s,index + 1,len);
				if(s[index]  == s[index - 1])
					ans += solution(s,index + 2,len);
			}
			else
				ans  += solution(s,index + 1,len);*/
			int ans = 0;
			// ans += solution(s,index,len);  写不写  ➕ 都无所谓  因为是这是第一个  这很简单
			ans = solution(s,index + 1,len);
			/*
			 * 注意 这些 逻辑
			 */
			if(index + 1 < len && s[index] ==s[index + 1])
				ans += solution(s,index + 2,len) % cons;
			if(index + 2 < len && s[index] == s[index + 1] && s[index +2] == s[index]) {
				ans += solution(s,index + 3,len) % cons;
			}
			if((s[index] == '7' && index + 3 < len && s[index] == s[index + 1] && s[index + 2] == s[index + 1])
					&& s[index + 3] == s[index]) {
				ans += solution(s,index + 4,len) % cons;
			}
			if((s[index] == '9' && index + 3 < len && s[index] == s[index + 1] && s[index + 2] == s[index + 1])
					&& s[index + 3] == s[index]) {
				ans += solution(s,index + 4,len) % cons;
			}
			return ans % cons;
		}
		/**
		 *  一维 dp
		 *  果然是  (int) 类型 溢出的 原因 (我敲)
		 *  因为 就  想不出来  其他的地方那里 会出错
		 *  把 ans 声明 成 long 最后 在 强转 一下 就可以了
		 *  22ms 
		 */
		static int solutionDp(String str) {
			char s [] = str.toCharArray();
			int len = str.length();
			int dp[]  = new int [len + 1];
			dp[len] = 1;
			for(int index = len -1 ;index >= 0;index--) {
				long ans = 0;
				ans = dp[index + 1] % cons;
				if(index +1 < len && s[index] == s[index + 1])
					ans += dp[index + 2] % cons ;
				if(index + 2 < len && s[index] == s[index + 1] && s[index] == s[index + 2])
					ans +=dp[index + 3] % cons;
				if((s[index] == '7' && index + 3 < len && s[index] == s[index + 1] && s[index + 2] == s[index + 1])
						&& s[index + 3] == s[index]) {
					ans += dp[index + 4] % cons;
				}
				if((s[index] == '9' && index + 3 < len && s[index] == s[index + 1] && s[index + 2] == s[index + 1])
						&& s[index + 3] == s[index]) {
					ans += dp[index + 4] % cons;
				}
				dp[index] = (int)(ans % cons);
			}
			
			return dp[0] % cons;
		}
		/**
		 * 
		 * 改变 取模 时候 的对象 
		 * 27ms 左右 
		 */
		static int solutionDpTest(String str) {
			char s [] = str.toCharArray();
			int len = str.length();
			int dp[]  = new int [len + 1];
			dp[len] = 1;
			for(int index = len -1 ;index >= 0;index--) {
				int ans = 0;
				ans = dp[index + 1] % cons;
				if(index +1 < len && s[index] == s[index + 1])
					ans =(ans + dp[index + 2]) % cons ;
				if(index + 2 < len && s[index] == s[index + 1] && s[index] == s[index + 2])
					ans = (ans + dp[index + 3]) % cons;
				if((s[index] == '7' && index + 3 < len && s[index] == s[index + 1] && s[index + 2] == s[index + 1])
						&& s[index + 3] == s[index]) {
					ans =(ans + dp[index + 4]) % cons;
				}
				if((s[index] == '9' && index + 3 < len && s[index] == s[index + 1] && s[index + 2] == s[index + 1])
						&& s[index + 3] == s[index]) {
					ans =(ans +  dp[index + 4]) % cons;
				}
				dp[index] = ans % cons;
			}
			
			return dp[0] % cons;
		}
}
